/** 要求abs(nums[i] - nums[i+1]) <= 1
 * 求nums[index] 的最大值
 * @param {number} n 数组长度
 * @param {number} index 所求下标
 * @param {number} maxSum 数组最大值
 * @return {number}
 * 设nums[index]=x，index 左侧的数组元素从x-1每次递减 1，右侧同理
 * 如1 1 2 3 2 1 1 ，可以找到一个最小的数组总和
 */
// 二分法端点选择
// 如果 right = mid-1   mid 就是 Math.floor((left + right + 1) / 2)
// 如果 right = mid     mid 就是 Math.floor((left + right) / 2)
var maxValue = function (n, index, maxSum) {
    // 求cnt个元素，最大值为x的数组的和
    var sum = function (x, cnt) {
        if (x >= cnt) {
            // 数组从x递减到x-cnt+1
            return (x + x - cnt + 1) * cnt / 2
        } else {
            // 数组从x递减到1,且有cnt-x个剩余的1
            return (x + 1) * x / 2 + (cnt - x) * 1
        }
    }

    // 数组最大值位于1到maxSum之间
    let left = 1, right = maxSum
    while (left < right) {
        let mid = Math.floor((left + right + 1) / 2)
        // 以mid为中心，左右两边数组的和
        if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
            left = mid
        } else {
            right = mid - 1
        }
    }

    return left
};

// 循环写法2
// 加等号
while (left <= right) {
    // 改mid计算方式
    let mid = Math.floor(left + (right - left) / 2)
    if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
        // 改left计算方式
        left = mid + 1
    } else {
        right = mid - 1
    }
}
// 改返回数
return right